package com.demo.java.OD101_150.OD150;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最左侧冗余覆盖子串】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145740553
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 输入字符串 s1, s2 和整数 k
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        int k = in.nextInt();
        int slen = s1.length() + k;  // 目标子串长度

        // 如果 s2 的长度小于 s1 + k，直接输出 -1
        if (s2.length() < slen) {
            System.out.print("-1");
            return;
        }

        int[] countArr = new int[26];  // 用于统计 s2 子串字符的频次

        // 统计 s2 的前 slen 个字符的频次
        for (int i = 0; i < slen; i++) {
            countArr[s2.charAt(i) - 'a']++;
        }

        // 统计 s1 中各字符的频次
        int[] arrS1 = new int[26];
        for (char c : s1.toCharArray()) {
            arrS1[c - 'a']++;
        }

        char fChar = s2.charAt(0);  // 当前窗口的首字符
        // 遍历 s2，滑动窗口
        for (int i = 0; i <= s2.length() - slen; i++) {
            char nChar = s2.charAt(i + slen - 1);  // 当前窗口的尾字符
            if (i > 0) {
                countArr[fChar - 'a']--;  // 移除窗口的首字符
                countArr[nChar - 'a']++;  // 添加新的尾字符
                fChar = s2.charAt(i);  // 更新窗口的首字符
            }

            // 检查当前窗口是否包含 s1 的所有字符
            boolean can = true;
            for (int j = 0; j < 26; j++) {
                if (countArr[j] < arrS1[j]) {
                    can = false;  // 如果某个字符的频次小于 s1，说明不满足条件
                    break;
                }
            }

            if (can) {
                System.out.print(i);  // 输出当前窗口的起始位置
                return;
            }
        }

        System.out.print("-1");  // 如果没有找到符合条件的子串，输出 -1
    }

}